#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

class Solution {
	map<int, int> rank;
	vector<int> xsort;
	vector<int> height;

	void prepare(vector<vector<int>> &buildings)
	{
		for (int i = 0; i < buildings.size(); i++) {
			xsort.push_back(buildings[i][0]);
			xsort.push_back(buildings[i][1] - 1);
			xsort.push_back(buildings[i][1]);
		}
		sort(xsort.begin(), xsort.end());
		xsort.erase(unique(xsort.begin(), xsort.end()), xsort.end());

		for (int i = 0; i < xsort.size(); i++) {
			rank[xsort[i]] = i;
		}

		for (int i = 0; i < buildings.size(); i++) {
			buildings[i][0] = rank[buildings[i][0]];
			buildings[i][1] = rank[buildings[i][1] - 1];
		}

		sort(buildings.begin(), buildings.end());
	}

    public:
	vector<vector<int>> getSkyline(vector<vector<int>> &buildings)
	{
		prepare(buildings);
		int n = buildings.size();
		int m = xsort.size();

		priority_queue<pair<int, int>> hpq;
		for (int i = 0, j = 0, hi = 0; i < m; i++) {
			for (; j < n && buildings[j][0] <= i; j++) {
				hpq.push({ buildings[j][2], buildings[j][1] });
			}

			while (!hpq.empty() && hpq.top().second < i) {
				hpq.pop();
			}

			hi = hpq.empty() ? 0 : hpq.top().first;
			height.push_back(hi);
		}

		vector<vector<int>> ans;
		for (int i = 0, pre = -1; i < m; i++) {
			if (height[i] != pre) {
				ans.push_back({ xsort[i], height[i] });
			}
                        pre = height[i];
		}

		return ans;
	}
};

int main()
{
	vector<vector<int>> buildings = { { 2, 9, 10 }, { 3, 7, 15 }, { 5, 12, 12 }, { 15, 20, 10 }, { 19, 24, 8 } };
	vector<vector<int>> ans = Solution().getSkyline(buildings);
	for (auto v : ans) {
		cout << '[' << v[0] << ',' << v[1] << "] ";
	}
	cout << endl;
	return 0;
}